package interview.topk;

import java.util.ArrayList;
import java.util.Stack;

public class TopK {
	public ArrayList<Integer> run(int[][] sortedArrays, int k) {
		
		ArrayList<Stack<Integer>> arrays = new ArrayList<Stack<Integer>>();
		for(int i = 0; i < sortedArrays.length; i++) {
			Stack<Integer> array = new Stack<Integer>();
			for(int j = sortedArrays[i].length - 1; j >= 0; j--) {
				array.push(sortedArrays[i][j]);
			}
			arrays.add(array);
		}
			
		ArrayList<Integer> topkResult = new ArrayList<Integer>();
		Heap<Stack<Integer>> sheap = new Heap<Stack<Integer>>(arrays, new StackComparator());
		for(int i = 0; i < k; i++) {
			Stack<Integer> s = sheap.min(); 
			topkResult.add(s.peek());
			s.pop();
		}
		
		return topkResult;
	}
}
